package suanfa;

/**
 * 中间扩散法
 */
public class HuiWenSolution
{
    public String longestPalindrome(String s) {

        if (s == null || s.length() <= 1)
            return s;
        int n = s.length();
        char[] cs = s.toCharArray();
        int max = 1;
        int maxIndex = 0;
        for (int i = 0; i < n; i++) {
            int l = i, r = i;
            while (r < n - 1 && cs[r] == cs[r + 1])
                r++;
            while (l >= 0 && r <= n - 1 && cs[l] == cs[r]) {
                l--;
                r++;
            }
            // 归位
            l++;
            r--;
            if (r - l + 1 > max) {
                max = r - l + 1;
                maxIndex = l;
            }
        }
        return s.substring(maxIndex, maxIndex + max);

    }

    public static void main(String[] args)
    {
        HuiWenSolution solution = new HuiWenSolution();
        String s = solution.longestPalindrome("bb");
        System.out.println(s);
    }


    /**
     * 自己再写一遍
     */
    public static String huiWenSolution(String s)
    {
        if (s==null || s.length()<=1)
        {
            return s;
        }
        int length = s.length();
        int max = 1;
        int maxIndex = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < length; i++)
        {
            int start=i,end = i;
            while (start < length - 1 && chars[end] == chars[end + 1])
            {
                end++;
            }
            while (start >= 0 && end <= length - 1 && chars[start] == chars[end])
            {
                start--;
                end++;
            }

            start++;
            end--;
            if (end - start + 1 > max)
            {
                max = end - start + 1;
                maxIndex = start;
            }

        }

        return s.substring(maxIndex,max+maxIndex);
    }
}
